1. Technical Field of the Invention
The present invention relates to Finite Impulse Response (FIR) Digital Filters. More specifically the invention relates to an efficient implementation for Finite Impulse Response filters in a multi-processor architecture.
2. Description of Related Art
Finite Impulse Response (FIR) filters are an important and widely used form of a digital filter. FIR filters are used in numerous real time applications including telecommunication, particularly for the generation of constant phase delay characteristics. In addition, signal processing applications requiring an interpolation and decimation function incorporate FIR filtration as an integral part of the process.
The output sample of a FIR filter is a convolution summation of input samples and the impulse response of the filter. The output, y(n) of a causal FIR filter can be written as:
      y    ⁡          (      n      )        =            ∑              k        =        0                    H        -        1              ⁢                  h        ⁡                  (          k          )                    *              x        ⁡                  (                      n            -            k                    )                    Where:                H is the total number of filter coefficients and n=0, 1, 2, 3 . . . for different values of n, the output sample of the filter can be obtained;        h(k) is the impulse response of the filter. Filter coefficients are determined for various values of k. The value of k can never be negative for a causal system; and        x(m) is the input sample, m=n−k as shown in the equation above. The value of m can never be negative for a causal system.                    As stated by the above equation, the coefficients are multiplied with the appropriate input samples and summed (i.e., accumulated) for obtaining a particular output sample. For N number of input samples and H number of coefficients, the required number of multiplications for a given output sample is H. The saturation point occurs at the Hth output sample as shown in FIG. 1. The H number of multiplications are necessarily required if all the H coefficients are unique.                        
Compared to other filters, FIR filters offer the following advantages: FIR filters are simple to implement and design. Linear-phase filters that delay the input signal, without causing phase distortion, can be easily realized using FIR filters. FIR filters do not employ any feedback and hence present fewer difficulties in practical implementation. The absence of feedback also simplifies design by making it possible to use finite precision arithmetic. Multi-rate applications such as “decimation” (reducing the sampling rate), “interpolation” (increasing the sampling rate), can be realized best by FIR filters.
FIR filters can be easily implemented using fractional arithmetic unlike other types of filters in which it is difficult to do so. It is always possible to implement a FIR filter using coefficients with a magnitude of less than 1.0 as the overall gain of the FIR filter can be adjusted at its output. All the above advantages make FIR filters preferable for fixed-point Digital Signal Processors (DSPs).
The conventional approach of FIR filter implementation utilizes a delay line (m=n−k, as in the equation above), resulting in increased memory requirements and slower computation.
U.S. Pat. No. 5,732,004 describes an algorithm for FIR filtering. It proposes a method of decimating and/or interpolating a multi-bit input signal in which n/2 additions are performed, where ‘n’ is the number of bits in each filter coefficient. Scaling and multiplication of data with coefficients is performed using standard DSP architecture using coefficient values and associated scaling factors stored in memory. The coefficients are stored in coded form, and are then decoded prior to multiplication by the data values. A delay line is essential for the implementation of this method.
U.S. Pat. Nos. 6,260,053 and 5,297,069 describe methods and implementations that utilize delay lines for FIR filter implementation. Moreover, none of these methods provides linear scalability.